package ar.uba.fi.taller2.ftrs.Btree;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;

import ar.uba.fi.taller2.ftrs.Tree.Tree;


/******************************************************************************
 * <p>Title: CMSC420 </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2004</p>
 * <p>Company: </p>
 * @author sebastian rivas
 * @version 1.0
 *****************************************************************************/

public class BTree implements java.io.Serializable, Tree {

  class IllegalOrderException extends Exception {
    IllegalOrderException(int order){
      super("Illegal order ("+order+") for B+ tree");
    }
  }
  class IllegalLeafSizeException extends Exception {
    IllegalLeafSizeException(int leafSize){
      super("Illegal leaf size ("+leafSize+") for B+ tree");
    }
  }

  private int num_keys;
  private int m_order;

  //private transient BSNode iNode = null; //iteration node
  private Comparator comparator = null;
  private transient BNode root = null;
  /**
   * The number of entries in the tree
   */
  private transient int bp_size = 0;
  private transient int LeafSize;

  /**
   * datos de las modificaciones estructurales del arbol
   */
  private transient int modCount = 0;

  private void incrementSize()   { modCount++; bp_size++; }
  private void decrementSize()   { modCount++; bp_size--; }
  
  private ArrayList<String> prints;
  private ArrayList<String> pseudos;

  /******************************************************************************
   * CONSTRUCTOR
   * @param comp Comparator
   * @param order int
   * @param leafSize int
   ****************************************************************************/
  public BTree(Comparator comp, int order){
	  int leafSize=order;
    num_keys    = order;

    if(comp==null)
    this.comparator=new Comparator(){
        public int compare(Object o1, Object o2){
            Comparable c1 = (Comparable)o1;
            return c1.toString().compareTo(o2.toString());
          }
        };
    else comparator = comp;

    /*if(order<3) throw new IllegalOrderException(order);
    if(leafSize<order) throw new IllegalLeafSizeException(leafSize);*/

    m_order     = order;
    LeafSize    = leafSize;
    
    prints		= new ArrayList<String>();
    pseudos		= new ArrayList<String>();
  }


  /******************************************************************************
   * CONSTRUCTOR
   * @param order int
   * @param leafSize int
   ****************************************************************************/
  public BTree(int order){
     this(null,order);
  }

  /****************************************************************************
   *
   * @return boolean
   * return if tree is empty
   ***************************************************************************/
  public boolean isEmpty(){

    return root == null;
  }

  /****************************************************************************
   * clear the bptree
   ***************************************************************************/
  public void clear(){
    root    = null;
    bp_size = 0;
  }

  /****************************************************************************
   *
   * @param key Object
   * @return boolean
   * verifica si el arbol tiene Keys
   * ***************************************************************************/
  public boolean containsKey(Object key){
     BNode node   = root;
     while (node!=null) {
         int i = 0;
         if(node.getType() == BNode.LEAF ){
             return ((BLeafNode)node).containsKey(key)!=null;
         }
         for (; i<node.size()-1; i++) {
             if (compare(key,node.getKeyAt(i))==0) {
                 return true;
             } else if (compare(key,node.getKeyAt(i))<=0) {
                 break;
             }
         }
         node   = (BNode) node.getItemAt(i);
         if(node.getType() == BNode.LEAF){
             return ((BLeafNode)node).containsKey(key)!=null;
         }
     }

      return false;
   }

  /****************************************************************************
  *    Object remove(Object key)
  *    Removes the mapping for this key from this map if it is present
  *    @throws Exception 
  ****************************************************************************/
  public void remove(Object key) throws Exception {
	  
	  if(this.isEmpty()) return;

	  root.remove(key);

	  decrementSize();
	  
	  if(this.bp_size==0) {
		  root = null;
		  return;
	  }
	  
	  if(root.size()==0){
		  if(root.getType() == BNode.GUIDE) {
			  root = (BNode)root.getItemAt(0);
		  } else {
			  root = null;
		  }
	  }
  }

  /****************************************************************************
      Object put(Object key,Object value)
      Associates the specified value with the specified key in this map
  ****************************************************************************/
  public Object put(Object key, Object value){
    Entry rec = new Entry();
    BNode newNode = null;
    rec.setKey(key);
    rec.setValue(value);

    if(root==null){
      root = new BLeafNode(comparator, LeafSize, true, this);
    }
    newNode = root.put(rec);

    if(root.inOverflow()) {
    	 int splitPos = (int)Math.round((root.size()-1)/2.0);
    	 
    	 Object promoted = root.getPromoted(splitPos);
    	 BNode nw = root.splitAt(splitPos);
    	 BGuideNode newRoot = new BGuideNode(comparator,num_keys,LeafSize, true, this);
    	 newRoot.append(root, null);
    	 newRoot.append(nw, promoted);
    	 root = newRoot;
    }

    incrementSize();
    if(newNode==null)
      return root;
    else
      return newNode;

  }

  /*****************************************************************************
  * Returns the height of the bptree
  *****************************************************************************/
    private int getHeight() {
	    BNode p  = root;
	    int height = 0;
	    if (p != null) {
		    if(p.getType() == BNode.LEAF)
		    	return 1;
		    while(p.getItemAt(0)!= null){
			    height++;
			    if(p.getType() == BNode.LEAF) break;
			    p = (BNode)p.getItemAt(0);
		    }
	    }
	    return height;
    }

    /**************************************************************************
     * PrintXML outputs the tree in XML format
     *
     *************************************************************************/

    public void printXML(){
      System.out.println("<bptree cardinality=\""+bp_size+"\" height=\""
       +getHeight()+"\" order=\""+m_order+"\" leafSize=\""+LeafSize +"\">");
      if (root != null)
    	  root.printXML();
      System.out.println("</bptree>");
    }

    /**************************************************************************
     * PrintXML outputs the tree in XML format file 
     * @throws IOException 
     *
     *************************************************************************/

    public void printXML(BufferedWriter file) throws IOException{
    	 	String str="<bptree cardinalidad=\""+bp_size+"\" altura=\""
		       +getHeight()+"\" orden=\""+m_order+"\" tamanoHoja=\""+LeafSize +"\">";
			file.write(str);
			root.printXML(file);
			file.write("</bptree>");
    }
    public void printXML(String str){
        FileWriter fileWriter;
    	try {
    		fileWriter = new FileWriter(str, false);
    		BufferedWriter file = new BufferedWriter(fileWriter);
    	    this.printXML(file);
    		file.close();
    	} catch (IOException e) {
    		// TODO Auto-generated catch block
    		e.printStackTrace();
    	}
    }

   // solo para testing
    void Print() {
            if (root.size()>0 ) {
                    root.Print("");
            }
  }

  /****************************************************************************
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
                         CLASS BSTREE.ENTRY
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
  ****************************************************************************/


  static class Entry {
    private Object  key;
    private Object  data;
    private Entry   left;
    public  Entry   right;
    public  BNode  parent = null;
    public  int     rec_index = 0;


    /****************************************************************************
        Constructor
     ****************************************************************************/
    public Entry() {
      key   = new Object();
      data  = new Object();
      left  = null;
      right = null;
    }

    /****************************************************************************
       Constructor TRecord(Object dataKey, Object dataType)
    ****************************************************************************/

    public Entry(Object dataKey, Object dataType){

      key  = dataKey;
      data = dataType;

    }
        /**
         * Returns the key corresponding to this entry.
         *
         * @return the key corresponding to this entry.
         */
        public Object getKey(){
          return key;
        }

        public Object setKey(Object val){
          Object old = new Object();
          old = key;
          key = val;
          return old;
        }


        /**
         * Returns the value corresponding to this entry.  If the mapping
         * has been removed from the backing map (by the iterator's
         * <tt>remove</tt> operation), the results of this call are undefined.
         *
         * @return the value corresponding to this entry.
         */
        public Object getValue(){
          return data;
        }

        /**
         * Replaces the value corresponding to this entry with the specified
         * value (optional operation).  (Writes through to the map.)  The
         * behavior of this call is undefined if the mapping has already been
         * removed from the map (by the iterator's <tt>remove</tt> operation).
         *
         * @param value new value to be stored in this entry.
         * @return old value corresponding to the entry.
         *
         * @throws UnsupportedOperationException if the <tt>put</tt> operation
         *	      is not supported by the backing map.
         * @throws ClassCastException if the class of the specified value
         * 	      prevents it from being stored in the backing map.
         * @throws    IllegalArgumentException if some aspect of this value
         *	      prevents it from being stored in the backing map.
         * @throws NullPointerException the backing map does not permit
         *	      <tt>null</tt> values, and the specified value is
         *	      <tt>null</tt>.
         */
      public Object setValue(Object val){
          Object old = new Object();
          old = data;
          data = val;
          return old;
      }

    public void Print(){
      System.out.print(data);
    }

    /****************************************************************************
         Object setLeftLeaf();
        sert the left leaf
     ****************************************************************************/
    public  void setLeft(Entry node){
       left = node;
    }

    /****************************************************************************
         Object setRightLeaf();
        set the right leaf
     ****************************************************************************/
    public void setRight(Entry node){
       right = node;
    }

    public String toString(){
      return "<registro clave=\""+key +"\"/>";
    }

  }

  /****************************************************************************
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
                         CLASS ENTRYITERATOR
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
  &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
  ****************************************************************************/

    /**************************************************************************
     *
     * @param k1 Object
     * @param k2 Object
     * @return int
     * Compares two keys using the correct comparison method for this BSTree.
     *************************************************************************/
    private int compare(Object k1, Object k2) {
        return (comparator==null ? ((Comparable)k1).compareTo(k2)
                                 : comparator.compare(k1, k2));
    }
    public Object addKey(Integer key){
        return put(key,0);
		}
		
		public Object search(Integer key){
		        return null;
		        //not implemented
		        
		}
		public  Object remove(Integer key){
		        try {
					remove((Object)key);
					return null;
				} catch (Exception e) {
					return null;
				}
		}
		private String imprimirXml(){
 		    return imprimirSVG();
 		  }
	   public ArrayList<String> imprimir(){
		   imprimirEstado("0");
		   return prints;
 		    
	   }
	   private void imprimirEstado(String str){
		   prints.add(this.imprimirSVG());
		   pseudos.add(str);
	   }
	   public ArrayList<String> getPseudos(){
		  return pseudos;
 		    
	   }
	   public void reset(){
			   pseudos=new ArrayList<String>();
			   prints=new ArrayList<String>();
	 		    
	    }

  
        private String imprimirSVG(){
   		   
     		 String result="<?xml version=\"1.0\" encoding=\"utf-8\"?><?xml-stylesheet href=\"xhtml-hedge.xsl\" type=\"text/xsl\"?><html xmlns=\"http://www.w3.org/1999/xhtml\">  <head>     </head>  <body>    	<p><span class=\"hedge\">";
     		 
     			if (root !=null )result+=root.imprimir();
     			result+="</span> </p> " ;
     			result+=root.imprimirHtml();
     			result+=" </body></html>";
     			    return result;
     			    
     	     }
}


